class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        t1 = []
        t2 = []
        t3 = []
        te = []
        s = ''
        for i in a:
            t1.append(i)
        for i in b:
            t2.append(i)
        if len(a) > len(b):
            for i in range(1,len(b)+1):
                t3.append(t1[-i]+t2[-i])
            for i in range(0, len(a)-len(b)):
                te.append(t1[i])
            for i in range(1,len(te)+1):
                t3.append(te[-i])
        elif len(a) < len(b):
            for i in range(1, len(a)+1):
                t3.append(t1[-i]+t2[-i])
            for i in range(0, len(b)-len(a)):
                te.append(t2[i])
            for i in range(1,len(te)+1):
                t3.append(te[-i])
        else:
            for i in range(1, len(a)+1):
                t3.append(t1[-i]+t2[-i])
        t3.append('0')
        for i in range(len(t3)):
            if t3[i] == '00' or t3[i] == '0':
                s += '0'
            elif t3[i] == '01' or t3[i] == '10' or t3[i] == '001'or t3[i] == '1':
                s += '1'
            elif t3[i] == '11' or t3[i] == '101' or t3[i] == '011':
                s += '0'
                t3[i+1] += '1'
            else:
                s += '1'
                t3[i+1] += '1'
        print(t3,s)
        t = ''
        if s[-1] == '0':
            for i in range(len(s)-1):
                t += s[i]
            return t[::-1]
        else:
            return s[::-1]
    

    def addBinary2(self, a, b):
    """
    :type a: str
    :type b: str
    :rtype: str
    """
    t1 = []
    t2 = []
    s1 = 0
    s2 = 0
    s3 = 0
    res = []
    rs = ''
    for i in a:
        t1.append(int(i))
    t1 = t1[::-1]
    for i in range(len(t1)):
        s1 += t1[i]*2**i
    for i in b:
        t2.append(int(i))
    t2 = t2[::-1]
    for i in range(len(t2)):
        s2 += t2[i]*2**i
    s3 = s1 + s2
    if s3 == 0:
        return '0'
    else:
        while s3 > 0:
            res.append(s3%2)
            s3 //= 2
        res = res[::-1]
        for i in res:
            rs += str(i)
        return rs